This invention relates to the field of search control systems and more particularly to exhaustive search systems and methods using space-filling curves.
When one or more search agents are controlled to exhaustively search an area, the search system must guarantee coverage of the entire search area in a finite amount of time. Optimally, multiple search agents can search an area in less time than one search agent. But, the use of multiple agents can be inefficient to coordinate, can have overlapping search regions, and can require re-coordination if one or more agents fail. This results in a need to provide coordination among multiple autonomous or semi-autonomous cooperating agents without sacrificing efficiency or imposing an undue agent-to-agent communication burden.
One area that is particularly applicable to multiple agents is exhaustive geographic search, or source mapping, requiring development of a complete map of all phenomena of interest within a defined geographic area, subject to the engineering constraints of efficiency, robustness, and accuracy.
Examples of a need for an exhaustive search of a geographic area include using multiple robots to locate all buried mines within a specified geographic region and using one or more robots to cover a region for some other purpose like mowing or fertilizing. It can be possible to build a robot that has the requisite sensors and navigation apparatus to do mine searches, thus removing humans from an extremely high-risk activity. But a single robot can be expensive and subject to damage from mines, rendering it useless. If less expensive robots could be built in quantity, it could be better to build a swarm of such robots that could cooperate to locate all the mines within a given geographic region. A three-dimensional geographic area can be searched in water by multiple undersea robot swimmers, in air by flying robots, and on land by climbing robots.
Pseudo-geographical searches of an n-dimensional space include software agent searches of cyberspace (for example, searches over a network of interconnected computers to locate all information matching a specified search criterion, general computer searches in a multiprocessing environment, and database searches across one or more network databases).
Search Systems
Hert et al. and Choset and Pignon teach obstacle avoidance but do not teach efficient coverage with multiple robots or robustness. See Hert et al., xe2x80x9cA Terrain-Covering Algorithm for an AUV,xe2x80x9d Autonomous Robots, 3:91-119, 1996; and Choset and Pignon, xe2x80x9cCoverage Path Planning: The Boustrophedon Cellular Decomposition,xe2x80x9d International Conference on Field and Service Robotics, Canberra, Australia, 1997, also available at http://voronoi.sbp.ri.cmu.edu/xcx9cchoset.
Kurabayashi et al. teaches multiple-robot sweeping but does not teach distributed control and robustness. See Kurabayashi et al., xe2x80x9cCooperative Sweeping by Multiple Mobile Robots,xe2x80x9d 1996 IEEE International Conference On Robotics and Automation, pp. 1744-1749, 1996.
Goldsmith and Robineff teach an information-exploitive search algorithm for precise localization of a target source within a given region using risk-taker alpha agents and conservative beta agents communicating under a decentralized coordination strategy called alpha-beta coordination. Goldsmith and Robinett do not teach an exhaustive search algorithm with guaranteed coverage of the entire search area in a finite amount of time. See Goldsmith and Robinett, xe2x80x9cCollective Search by Mobile Robots Using Alpha-Beta Coordination,xe2x80x9d Collective Robotics Workshop ""98, Agent World, Paris, 1998.
Exhaustive Search
Search applications exist where there is no a pror knowledge of the locations of a search target. One example application given previously is in searching for target mines within a given geographic region. Similarly, in another example search application, a cybersearch over a network of one or more interconnected computers can seek out the locations of target information without a piori knowledge of information location.
When numerous search agents are used in exhaustive search applications, each agent and the distributed search system for each agent needs to be efficient and robust, and the entire set of search agents needs to guarantee search coverage of the search area. If a search agent cannot complete its search task or if it cannot communicate completion of its search task, the search system needs to reliably detect such a condition and robustly compensate for the failure while completing the exhaustive search task in a finite amount of time. Searching by spiraling outward in a geographic search can guarantee coverage of the search area in a finite amount of time, but using more than one search agent cannot necessarily decrease that time. Searching by a random walk cannot even guarantee coverage in a finite amount of time. It can be inefficient to perform a random walk with robots because: there is no guarantee that a random walk for a robot does not retrace own path, no guarantee exists that the random walk will not cover ground covered by a neighbor, and no guarantee exists that the random walk can finish in a finite amount of time.
Exhaustive search applications result in a need for a search controller that is efficient, robust, and provides guaranteed search area coverage in a finite amount of time. Accordingly, there is an unmet need for a search system suitable for one or multiple search agents that can be used where an guaranteed exhaustive area search is required to be performed in a finite amount of time and which requires little or no communication or re-coordination if a search agent dies or becomes defective.
The present invention provides a search system suitable for controlling one or multiple agents to search an area utilizing a locator and a search controller, generating an exhaustive search pattern for the search area comprising a space-filling curve along which the agent travels. The search area can comprise a physical geography or a cyberspace search area. Robotic vehicles and software agents are both suitable for use with the present invention.
The present invention teaches a new search method for controlling a single agent or multiple agents to exhaustively search an area according to a space-filling curve. The search method utilizes input from a locator and searches the area until a termination condition is met.